描述

传送门：HihoCoder-1174拓扑排序·一

我们都知道大学的课程是可以自己选择的，每一个学期可以自由选择打算学习的课程。唯一限制我们选课是一些课程之间的顺序关系：有的难度很大的课程可能会有一些前置课程的要求。比如课程A是课程B的前置课程，则要求先学习完A课程，才可以选择B课程。大学的教务收集了所有课程的顺序关系，但由于系统故障，可能有一些信息出现了错误。现在小Ho把信息都告诉你，请你帮小Ho判断一下这些信息是否有误。错误的信息主要是指出现了”课程A是课程B的前置课程，同时课程B也是课程A的前置课程”这样的情况。当然”课程A是课程B的前置课程，课程B是课程C的前置课程，课程C是课程A的前置课程”这类也是错误的。

输入描述

第1行：1个整数T，表示数据的组数T(1 <= T <= 5)
接下来T组数据按照以下格式：
第1行：2个整数，N,M。N表示课程总数量，课程编号为1..N。M表示顺序关系的数量。1 <= N <= 100,000. 1 <= M <= 500,000
第2..M+1行：每行2个整数，A,B。表示课程A是课程B的前置课程。

输出描述

第1..T行：每行1个字符串，若该组信息无误，输出”Correct”，若该组信息有误，输出”Wrong”。

示例

输入

输出

1 2	Wrong Correct

题解

题目大意

中文题面

思路

先扫描所有点和边维护每一个点的入度值，复杂度O(N+M)。把入度为0的点加入队列Q中，当然有可能存在多个入度为0的点，同时它们之间也不会存在连接关系，所以按照任意顺序加入Q都是可以的。从Q中取出一个点p。对于每一个未删除且与p相连的点q，入度值-1；如果入读值为0，把q加入Q。不断重复第3步，直到Q为空。
最后剩下的未被删除的点，也就是组成环的点了。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdio>
#include <queue>
#include <cmath>
const int MAXN = 5*1e5, INF = 0x3f3f3f3f, MOD = 142857;
using namespace std;
int n, m, k, u, v, x;
int inq[MAXN];
vector<int> E[MAXN];

bool topsort(){
    queue<int> q;
    int num = 0;
    for(int i = 1; i <= n; i++){
        if(!inq[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int now = q.front();
        q.pop();
        num++;
        for(int i = 0; i < E[now].size(); i++){
            if(--inq[E[now][i]] == 0){
                q.push(E[now][i]);
            }
        }
    }
    if(num == n) return true;
    else return false;
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        memset(inq, 0, sizeof(inq));
        for(int i = 0; i <= n; i++) E[i].clear();
        for(int i = 0; i < m; i++){
            scanf("%d %d", &u, &v);
            E[u].push_back(v);
            inq[v]++;
        }
        if(topsort()) puts("Correct");
        else puts("Wrong");
    }
}

/*
2
2 2
1 2
2 1
3 2
1 2
1 3
*/